import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class kMeans {

	private String filePath;
	private String dataDelimiter;
	private int ignoreCol;
	private String notAvailable;
	
	private int dimension;
	private int cluster;
	private Cluster[] clusters;
	private List<DataPoint> dataPoints;
	
	private double eps;
	private double[] maxAttr;
	private double[] minAttr;
		
	public kMeans(String filePathToData, int cluster, int ignoreCol, String dataDelimiter, String notAvailable,  double eps) {
		/* set arguments */
		this.filePath = filePathToData;
		this.ignoreCol = ignoreCol;
		this.cluster = cluster;
		this.dataDelimiter = dataDelimiter;
		this.clusters = new Cluster[cluster];
		this.eps = eps;
		this.notAvailable = notAvailable;
		/* read input */
		this.readInput();
	}
	
	public void run(){
		this.initCluster();
		double maxClusterDistanceDelta = Double.MAX_VALUE;
		while(maxClusterDistanceDelta > this.getEps()) {
			this.organizeDataPoints();
			maxClusterDistanceDelta = this.adjustClusterCenters();
		}
	}
	
	private double adjustClusterCenters() {
		double maxDelta = Double.MIN_VALUE;
		
		for(Cluster cluster : this.getClusters()) {
			double delta = cluster.adjustCenter();
			if(delta > maxDelta)
				maxDelta = delta;
		}
		return maxDelta;
	}

	private void organizeDataPoints() {
		for(DataPoint dataPoint : this.getDataPoints()) {
			Cluster nearestCluster = null;
	        double curMinDistance = Double.POSITIVE_INFINITY;
	        for (int i = 0; i < clusters.length; i++) {
	        	Cluster currentCluster = clusters[i];
	        	double distanceToCluster = currentCluster.getCenter().getEuclideanDistanceTo(dataPoint);
	        	if (distanceToCluster < curMinDistance) {
	        		curMinDistance = distanceToCluster;
	                nearestCluster = currentCluster;
	        	}
	        }
	        if (nearestCluster != dataPoint.getCluster()) {
	        	if(dataPoint.getCluster() != null)
	        		dataPoint.getCluster().swapDataPoint(nearestCluster, dataPoint);
	        	else {
	        		dataPoint.setCluster(nearestCluster);
	        		nearestCluster.addDataPoint(dataPoint);
	        	}
	        }
		}
	}

	private void initCluster() {
		Random random = new Random();
		Cluster[] clusters = new Cluster[this.getCluster()];
		// generate new clusters with random centerpoints
		for(int i = 0; i < this.getCluster(); i++) {
			Cluster cluster = new Cluster(i, ""+(i+1));
			clusters[i] = cluster;
			//dat's pure random centers
//			double[] center = new double[this.getDimension()];
//			for(int j = 0; j < this.getDimension(); j++) {
//				center[j] = this.minAttr[j] +  ((this.maxAttr[j] - this.minAttr[j]) * random.nextDouble());
//			}
			// choose just a random datapoint
			DataPoint centerPoint = new DataPoint(this.getDataPoints().get(random.nextInt(this.getDataPoints().size())).getAttributes());
			cluster.setCenter(centerPoint);
		}
		this.setClusters(clusters);
	}

	private void readInput() {
		BufferedReader reader;
		try {
			reader = new BufferedReader(new FileReader(this.getFilePath()));
			String line = reader.readLine();
			// first get the dimension of the dataPoints
			int dimension = line.split(this.getDataDelimiter()).length;
			if( this.getIgnoreCol() > -1)
				dimension -= 1;
			this.dimension = dimension;	            
	        reader.close();
	        
			this.maxAttr = new double[this.getDimension()];
			this.minAttr = new double[this.getDimension()];
			for(int i = 0; i < this.getDimension(); i++) {
				this.maxAttr[i] = Double.NEGATIVE_INFINITY;
				this.minAttr[i] = Double.POSITIVE_INFINITY;
			}
			
	        this.dataPoints = new ArrayList<DataPoint>();
	        
	        reader = new BufferedReader(new FileReader(this.getFilePath()));
	        
	        // read all the lines and transform each to a dataPoint
	        while( (line = reader.readLine()) != null ) {
	        	
	        	String[] split = line.split(this.getDataDelimiter());
				if( this.getIgnoreCol() > -1) {
					String[] tmpSplit = new String[this.getDimension()];
					for (int i = 0; i < split.length; i++) {
						int j = i;
						if(i == ignoreCol)
							continue;
						if(i > ignoreCol)
							j = i - 1;
						tmpSplit[j] = split[i];
					}
					split = tmpSplit;
				}
	        	double[] tmp_attr = new double[this.getDimension()];
	        	for(int i = 0; i < split.length; i++){
	        		if(split[i].equals(this.getNotAvailable())) {
	        			tmp_attr[i] = Double.NaN;
	        		}
	        		else { 
	        			double val = Double.parseDouble(split[i]);
	        			tmp_attr[i] = val;
	        			if(val > this.maxAttr[i])
	        				this.maxAttr[i] = val;
	        			if(val < this.minAttr[i])
	        				this.minAttr[i] = val;
	        		}
	        	}
	        	DataPoint dataPoint = new DataPoint(tmp_attr);
	        	dataPoint.dimension = dimension;
	        	
	        	this.addDataPoint(dataPoint);
	        }
	        reader.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public void printClusters() {
		for(Cluster cluster : this.clusters)
			System.out.println(cluster);
	}
	
	public int getIgnoreCol() {
		return ignoreCol;
	}

	public String getNotAvailable() {
		return notAvailable;
	}

	public Cluster[] getClusters() {
		return clusters;
	}

	public void setClusters(Cluster[] clusters) {
		this.clusters = clusters;
	}

	public String getFilePath() {
		return filePath;
	}

	public String getDataDelimiter() {
		return dataDelimiter;
	}

	public int getDimension() {
		return dimension;
	}

	public int getCluster() {
		return cluster;
	}

	public List<DataPoint> getDataPoints() {
		return dataPoints;
	}
	
	private void addDataPoint(DataPoint dataPoint) {
		this.dataPoints.add(dataPoint);
	}

	public double getEps() {
		return eps;
	}

	public double[] getMaxAttr() {
		return maxAttr;
	}

	public double[] getMinAttr() {
		return minAttr;
	}

	public void presentCluster() {
		kMeansPresenter presenter = new kMeansPresenter(this);
		presenter.present();
	}

	public double compareTo(kMeans kMeans) {
		
		double N1 = 0;
		double N2 = 0;
		double N3 = 0;
		double N4 = 0;
		
		if(this.getCluster() != kMeans.getCluster()) {
			System.out.println("WARNING: Cluster count different!");
			System.out.println("Abort ...");
			return Double.NaN;
		}
		
		int clusterCount = this.getCluster();
		
		// init percentage array
		int[][] p = new int[clusterCount][clusterCount];
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
				p[i][j] = 0;
			}
		}

		//map clusterings
		for (int i = 0; i < this.getCluster(); i++) {
			Cluster cluster1 = this.getClusters()[i];
			for (int j = 0; j < this.getCluster(); j++) {
				Cluster cluster2 = kMeans.getClusters()[j];
				p[i][j] = cluster1.getSamePoints(cluster2);
			}
		}
		
		Integer[] matching = new Integer[clusterCount];
		
		// print percentage array
		for (int i = 0; i < p.length; i++) {
			int max = 0;
			int index = -1;
			for (int j = 0; j < p.length; j++) {
				if(p[i][j] > max) {
					max = p[i][j];
					index = j;
				}
			}
			matching[i] = index;
		}		
		
//		boolean cleanMatching;
//		boolean perfectMatching;
//		
//		Set<Integer> mySet = new TreeSet<Integer>(Arrays.asList(matching));
//		
//		if (mySet.size() != matching.length) {
//			cleanMatching = false;
//		} else {
//			cleanMatching = true;
//		}
//		
//		if (cleanMatching) {
//			perfectMatching = true;
//			for (int i = 0; i < matching.length; i++) {
//				if (this.getClusters()[i].getDataPoints().size() != kMeans.getClusters()[matching[i]].getDataPoints().size()) {
//					perfectMatching = false;
//				}
//			}
//		} else {
//			perfectMatching = false;
//		}
				
		double n = this.getDataPoints().size();
		
		double[] tmp_i = new double[p.length];
		double[] tmp_j = new double[p.length];
		for (int i = 0; i < tmp_j.length; i++) {
			tmp_i[i] = 0;
			tmp_j[i] = 0;
		}

		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					tmp_i[i] += p[i][j];
					tmp_j[j] += p[i][j];
			}
		}		
		
		//compute N1		
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					N1 += p[i][j] * (p[i][j]-1); 
			}
		}
		N1 *= 0.5;
		
		//compute N2
		double tmp_1 = 0;
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					tmp_1 += p[i][j] * p[i][j]; 
			}
		}
		double tmp_2 = 0;
		for (int i = 0; i < tmp_i.length; i++) {
			tmp_2 += tmp_i[i] * tmp_i[i];
		}
		double tmp_3 = 0;
		for (int j = 0; j < tmp_j.length; j++) {
			tmp_3 += tmp_j[j] * tmp_j[j];
		}		
		N2 = 0.5 * (n*n + tmp_1 - (tmp_2 + tmp_3));
		
		
		//compute N3
		N3 = 0.5 * (tmp_3 - tmp_1);
		
		//compute N4
		N4 = 0.5 * (tmp_2 - tmp_1);
		
//		return new double[]{N1, N2, N3, N4};
		return (N1 + N4)/(N1 + N2 + N3 + N4);
	}
	
}
